#include<cstring>
#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
using namespace std;
const int maxn=111;
int f[maxn][maxn];
int n;
int main()
{
	string s1,s2;
	while(cin>>s1>>s2)
	{
		memset(f,0x3f3f3f3f,sizeof(f));
		n=s1.size();
		for(int i=1;i<=n;i++)
			 f[i][i]=1;
		for(int i=n-1;i>=1;i--)
			for(int j=i+1;j<=n;j++)
			{
				if(s2[i-1]==s2[j-1])			
					f[i][j]=f[i][j-1];					
				for(int k=i;k<=j-1;k++)
					f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
			}
		int ans[maxn];
		ans[1]=(s1[0]==s2[0]?0:1);
		for(int i=2;i<=n;i++)
		{
			ans[i]=f[1][i];
			if(s1[i-1]==s2[i-1])
				ans[i]=min(ans[i],ans[i-1]);		
			for(int j=1;j<=i-1;j++)
				ans[i]=min(ans[i],ans[j]+f[j+1][i]);
			
		}
		cout<<ans[n]<<endl;
	}
	return 0;
}

	
